import java.util.Stack;

public class Day19 {


    public static void main(String[] args) {
        StringBuilder s1 = new StringBuilder();
        //multiply("11111","0");
        backspaceCompare("y#fo##f","y#f#o##f");
    }


    public static boolean backspaceCompare(String s, String t) {
        Stack<Character> stack = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        StringBuilder ret = new StringBuilder();
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(stack.isEmpty()&&ch!='#') {
                stack.push(ch);
            }else {
                if(ch == '#') {
                    if(!stack.isEmpty())
                        stack.pop();
                }else {
                    stack.push(ch);
                }
            }
        }
        while(!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        s = ret.toString();
        StringBuilder ret2 = new StringBuilder();

        for(int i=0;i<t.length();i++) {
            char ch = t.charAt(i);
            if(stack2.isEmpty()&&ch!='#') {
                stack2.push(ch);
            }else {
                if(ch == '#') {
                    if(!stack2.isEmpty())

                        stack2.pop();
                }else {
                    stack2.push(ch);

                }
            }
        }
        while(!stack2.isEmpty()) {
            ret2.append(stack2.pop());
        }
        t = ret2.toString();
        if(t.equals(s)) return true;
        return false;
    }
    //删除字符串相邻重复项
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder ret = new StringBuilder();
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(stack.isEmpty()) {
                stack.push(ch);
            }else {
                if(stack.peek() == ch) {
                    //双双丢弃
                    stack.pop();
                }else {
                    //入栈
                    stack.push(ch);
                }
            }
        }
        while(!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        return ret.reverse().toString();
    }

    //字符串相乘
    public static String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) return new String("0");
        int m = num1.length(),n = num2.length();
        //1.逆序
        StringBuilder s1 = new StringBuilder(num1);
        StringBuilder s2 = new StringBuilder(num2);
        s1.reverse();
        s2.reverse();
        //2.计算相乘
        int[] tmp = new int[m+n-1];
        for(int i=0;i<s1.length();i++) {
            //i乘以j的的每一位
            int a = (int)(s1.charAt(i) - '0');//将一个字符数字转成整型数字
            for(int j=0;j<s2.length();j++) {
                int b = (int)(s2.charAt(j) - '0');
                tmp[i+j] += (a*b);
            }
        }
        //3.处理进位
        StringBuilder ret = new StringBuilder();
        int t = 0;
        int i=0;
        while(t!=0 || i<tmp.length) {
            if(i>=tmp.length) {
                ret.append((char)(t%10+'0'));
                break;
            }
            t += tmp[i];
            ret.append((char)(t%10+'0'));
            t /= 10;
            i++;
        }
        //4.前导0问题
        ret.reverse();
        return ret.toString();
    }
}
